import java.util.*;
import java.util.Map.Entry;
/**
 * 
 * @author darin
 * Most of the code is copy-paste from Professor M. Alden's BreadthFirstSearch code
 * with small modifications made to change function to UniformCostSearch
 */
public class UniformCostSearch {
/*
 * Maybe create a puzzle class that implements StateWithCost and comparable. Make the individual
 * puzzle types extend puzzle.	
 */
	
	public static List<StateWithCost> solve(StateWithCost start, StateWithCost goal) {
		PriorityQueue<PathNode> frontier = new PriorityQueue<PathNode>();

		Map<PathNode,PathNode> exploredAndFrontier = new HashMap<>();
		// The total number of nodes explored.
		int nodesExplored = 0;
		// The total number of nodes that have been in the frontier.
		int nodesInFrontier = 0;
		// The total number of nodes created.
		int nodesCreated = 0;
		
		//frontier.add(start);
		PathNode first = new PathNode(start, null, 0);
		
		frontier.add(first);
		exploredAndFrontier.put(first, null);
		nodesInFrontier++;
		
		while (!frontier.isEmpty()) {
			PathNode pathNode = frontier.remove();
			StateWithCost node = pathNode.getPuzzleNode();
			nodesExplored++;
			if(node.equals(goal))
			{
				System.out.println("Nodes Explored " + nodesExplored);
				System.out.println("nodesInFrontier " + nodesInFrontier);
				System.out.println("nodesCreated " + nodesCreated);
				return getSolutionPath(pathNode,exploredAndFrontier );
			}
			//get this nodes neighbors
			Map<StateWithCost,Double> childMap = node.getNeighborsWithCost();
			nodesCreated++;
						
			// get the list of childrenwith costs so we can iterate over it
			Set<Entry<StateWithCost, Double>> childSet = childMap.entrySet();
			Iterator<Entry<StateWithCost, Double>> itr = childSet.iterator();

			while(itr.hasNext()){
				Entry<StateWithCost,Double> childEntry = itr.next();
				StateWithCost child = childEntry.getKey(); // to acquire the child (neighbor) Object
				// PathNode hold the child, maintains the path via a link
				// to the parent PathNode, and is comparable via cost so that
				// it works with the priority queue
				PathNode newNode = new PathNode(child, pathNode, 
						pathNode.getCost() + childMap.get(child));
				frontier.add(newNode); // because we'll want to expand this nodes neighbors later
				exploredAndFrontier.put(newNode, pathNode); // to keep a record of the path
				nodesInFrontier++;
			} // end while(itr.hasNext())
		} // end While(!Frontier.isEmpty())
		// if we're here, we didn't find a solution
		return null;
	}// end solve() 
	
	/**
	 *  Reverse engineers the path using PathNode's getParent() method,
	 *  returns the path as a linked list of StateWithCost Objects
	 * @param pathNode
	 * @param parentMap
	 * @return A list of StateWithCost objects that comprise the path to the solution
	 */
	public static List<StateWithCost> getSolutionPath(PathNode pathNode, Map<PathNode,PathNode> parentMap) {
		LinkedList<StateWithCost> path = new LinkedList<>();
		
		while (pathNode != null) {
			StateWithCost puzzleNode = pathNode.getPuzzleNode();
			path.addFirst(puzzleNode);
			pathNode = parentMap.get(pathNode);
		}
		return path;
	}
	
	/**
	 * Provides a wrapper for StateWithCost objects that maintains a record of
	 * the path via a link to a parent PathNode object, Maintains to total cost 
	 * of the path via a cost field, and is comparable so that it works with 
	 * the priority queue
	 * @author darin
	 *
	 */
	private static class PathNode implements Comparable{
		double cost;
		PathNode parent = null;
		StateWithCost puzzleNode;
		
		public PathNode(StateWithCost puzzleNode, PathNode parent, double cost)
		{
			this.puzzleNode = puzzleNode;
			this.parent = parent;
			this.cost = cost;
		}
		/**
		 * @return the cost
		 */
		public final double getCost() {
			return cost;
		}
		
		/**
		 * @return the puzzleNode
		 */
		public final StateWithCost getPuzzleNode() {
			return puzzleNode;
		}
		@Override
		public int compareTo(Object o) {
			if(! (o instanceof PathNode))
	            throw new ClassCastException("Invalid object");
			else return (int)(getCost() - ((PathNode)o).getCost());
		}	
	}
}